package leetcode.sword;
import datastruct.tree.TreeNode;

public class Solution26 {

    public static void main(String[] args) {
//        TreeNode A = new TreeNode();
//        TreeNode B = new TreeNode();
//        A = new Utils(new int[]{4,2,4,8,-1,-1,9,-1,-1,5,-1,-1,3,6,-1,-1,7,-1,-1})
//                .createTreeNode(A);
//        B = new Utils(new int[]{4,8,-1,-1,9,-1,-1})
//                .createTreeNode(B);
//        System.out.println(new Solution26().isSubStructure(A, B));
        String s = ""+"null,"+12+","+"null,";
        String[] res = s.split(",");
        System.out.println(res[0].equals("null"));
    }

    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A==null||B==null) return false;
        //对以A的每个节点为根的树与B比较
        boolean flag = isEqual(A, B);
        if(flag) return flag; //剪枝
        if(A.left!=null) flag = flag || isSubStructure(A.left, B);
        if(flag) return flag; //剪枝
        if(A.right!=null) flag = flag || isSubStructure(A.right, B);
        return flag;
    }

    public boolean isEqual(TreeNode ANode, TreeNode B){
        if(ANode==null&&B==null){
            return true; //比较到末尾了
        }else if(ANode!=null && B!=null){ //都不空，继续比
            return ANode.val==B.val && isEqual(ANode.left, B.left)
                    && isEqual(ANode.right, B.right); //根节点值相同，
        }else{//一个空，另一个不空，没法比
            return false;
        }
    }

}
